$QvQ$ 之前就对这个东西感兴趣，然后被一堆公式踩爆，这样高逼格的名字简直让人无法靠近。终于在 $1$ 月的时候，教练扯着我搞这个，没想到一天左右就会了。
我们进入正题。
0XFF—-FFT是啥?
FFT是一种DFT的高效算法，称为快速傅立叶变换（fast Fourier transform），它根据离散傅氏变换的奇、偶、虚、实等 特性，对离散傅立叶变换的算法进行改进获得的。 —-百度百科
对于两个多项式 $F(x)$ 和 $G(x)$ ，要求你将他们乘起来。
那还不简单？直接暴力相乘啊：
设 $F(x)$ 的系数数列为 $C$。
$F(x) \times G(x) = C_nx^nG(x) + C_{n-1}x^{n-1}G(x) + C_{n-2}x^{n-2}G(x) \cdots C_2x^2G(x) + C_1x^1G(x) + C_0G(x)$
这样下来需要做做 $n$ 次单项式乘多项式，每次的时间复杂度 $O(n)$ ，则总复杂度高达 $O(n^2)$
基本上 $n$ 上了$4000$ 就会被卡吧……那怎么提速呢？
这就需要我们伟大而又神奇的神器：$FFT$ (快速博立叶变换)
复杂度就只有 $O(nlogn)$ 了。
0X1F—-FFT的前置知识.
1.复数是什么?
我们把形如 $z=a+bi$（ $a,b$ 均为实数）的数称为复数，其中 $a$ 称为实部， $b$ 称为虚部， $i$ 称为虚数单位。当虚部等于零时，这个复数可以视为实数；当z的虚部不等于零时，实部等于零时，常称z为纯虚数。复数域是实数域的代数闭包，即任何复系数多项式在复数域中总有根。 复数是由意大利米兰学者卡当在十六世纪首次引入，经过达朗贝尔、棣莫弗、欧拉、高斯等人 的工作，此概念逐渐为数学家所接受。 —-百度百科
想必大家都知道实数是啥(不知道重读幼儿园吧……)，实数位于数轴上，就像下图这样：
我们稍微观察一下，$1$ 是怎么变到 $-1$ 的呢？
在数轴上转了 180°。
如果，是 90° 的话，会发生什么呢？
这个时候，会转到 $0$ 上面的位置，但是那里，好像没有数啊!
不对，其实是有的，只不过这个数不在实数轴上，而是在虚数轴上！
虚数轴的单位是 $i$ ，我们可以这么表示：
嗯，对。这显然是一个平面坐标系。现在我们的数仅限于数轴上，如果是这个平面坐标系上的一个点怎么表达呢？
对于下面的红色点：
这个点的坐标很容易的可以得到：$(2,i)$ ，也可以表示成 $2+i$ .
你没猜错！这个就叫复数！
一个很重要的结论：复数相乘时，模长相乘，幅角相加！
2.点值表示法是什么?
我们用一个二维平面坐标系，在上面画 $N+1$ 个点，最终可以解出一个 $n$ 元的函数。证明略。
同样，我们可以用 $N-1$ 个点来表达一个多项式。
因为点值相乘的复杂度只有 $O(n)$ 显然优秀许多。
3.单位根是什么?
*n次单位根(n为正整数)是n次幂为1的复数!
*n次单位根(n为正整数)是n次幂为1的复数!
*n次单位根(n为正整数)是n次幂为1的复数!
我们先在复平面上画个点，就像这样：
Ta叫做单位圆。
圆边上的任意一点的模长都是 $1$.
只有单位圆上的点表示的复数才有可能成为$n$次单位根!
单位根的基本符号：$ω$
一个单位圆，我们将它切成 $n$ 份，从 $(1,0)$ 开始旋转，每次旋转 $\frac{1}{n} \times 360$ 度，每次旋转后的点都记为 $ω_{n}^{k}$，特别的，$ω_{n}^{0}$ 和 $ω_{n}^{n}$ 都是 $(1,0)$ 点。
还有，当 $k>=n$ 或者 $k<0$ 时，$ω_{n}^{k}$ 也是合法的。
单位根的性质：
$1.$ 对于任意的 $n$ , $ω_{n}^{0}$ 都为 $(1,0)$ 点。
$2.$ $ω_{n}^{a} \times ω_{n}^{b} = ω_{n}^{a+b} $
$3.$ $ω_{an}^{ak} = ω_{n}^{k} $
$4.$ $(ω_{n}^{x})^y = (ω_{n}^{y})^x $
$5.$ $ω_{n}^{k+n/2} = -ω_{n}^{k} $ if(n%2==0)
0X2F—-FFT的求解过程.
- 分治思想很重要！
我们将多项式 $F(x)$ 按位置分成两块。
那么变成了(保证n是2的正整数次幂)：
$F(x) = (C_0+C_2x^2+C_4x^4+ \cdots +C_{n-2}x^{n-2}) + (C_1x+C_3x^3+C_5x^5+ \cdots +C_{n-1}x^{n-1})$
设两个多项式 $F1(x),F2(x)$。
$F1(x) = C_0+C_2x+C_4x^2+ \cdots +C_{n-2}x^{n/2-1}$
$F2(x) = C_1x+C_3x+C_5x^2+ \cdots +C_{n-1}x^{n/2-1}$
则我们可以得出：
$F(x) = F1(x^2) + F2(x^2) \times x$
设 $k<n/2$ ， 将 $ω_{n}^{k}$ 带入多项式 $F(x)$.
$F(ω_{n}^{k}) = F1((ω_{n}^{k})2) + F2((ω_{n}^{k})^2) \times ω_{n}^{k}$
简化得： $F(ω_{n}^{k}) = F1(ω_{n/2}^{k}) + F2(ω_{n/2}^{k}) \times ω_{n}^{k}$
再假设 $k<n/2$ ，将 $ω_{n}^{k+n/2}$ 带入多项式 $F(x)$.
$F(ω_{n}^{k+n/2}) = F1((ω_{n}^{k+n/2})2) + F2((ω_{n}^{k+n/2})^2) \times ω_{n}^{k}$
$F(ω_{n}^{k+n/2}) = F1(ω_{n}^{2k+n}) + F2(ω_{n}^{2k+n}) \times ω_{n}^{k+n/2}$
$F(ω_{n}^{k+n/2}) = F1(ω_{n}^{2k}) + F2(ω_{n}^{2k}) \times ω_{n}^{k+n/2}$
$F(ω_{n}^{k+n/2}) = F1(ω_{n/2}^{k}) + F2(ω_{n/2}^{k}) \times ω_{n}^{k+n/2}$
$F(ω_{n}^{k+n/2}) = F1(ω_{n/2}^{k}) - F2(ω_{n/2}^{k}) \times ω_{n}^{k}$
比较一下两个式子：
- $F(ω_{n}^{k}) = F1(ω_{n/2}^{k}) + F2(ω_{n/2}^{k}) \times ω_{n}^{k}$
- $F(ω_{n}^{k+n/2}) = F1(ω_{n/2}^{k}) - F2(ω_{n/2}^{k}) \times ω_{n}^{k}$
等式右边只有一个负号的差别!
这两个式子很关键！
0X3F—-FFT的代码实现.
对于复数的使用
虽然 $C++ STL$ 里面有复数 $(complex)$ 但是太慢不建议大家使用。
你可以自己手打 $complex$
- 手打的 $complex$ :
1 | struct complex{complex(double a=0,double b=0){x=a,y=b;}double x,y;}; |
- FFT:
1 | complex a[N],b[N]; |
$Code$ 中提到的公式是这两项：
- $F(ω_{n}^{k}) = F1(ω_{n/2}^{k}) + F2(ω_{n/2}^{k}) \times ω_{n}^{k}$
- $F(ω_{n}^{k+n/2}) = F1(ω_{n/2}^{k}) - F2(ω_{n/2}^{k}) \times ω_{n}^{k}$
对于文中的”坐标的变换”：
我们依旧来看单位圆：
实际上，这个坐标的变换，直接用园中的三角形，运用三角函数就可以得出解了。
过程略.
最后我们得到的结果是：$ω_{n}^{1} = (cos(\frac{2π}{n}),sin(\frac{2π}{n}))$
求出 $ω_{n}^{1}$ 后将它乘 $n$ 次，可以得到：$ {ω_{n}^{0},ω_{n}^{1},ω_{n}^{2},ω_{n}^{3},ω_{n}^{4},ω_{n}^{5} \cdots ω_{n}^{n-1}} $
贴出最终的代码：
1 |
|
听说可以优化，那啥的我还不会，就到这吧.
过了一会儿……
“原来FFT小优化这么简单啊!”
0X4F—-FFT的一些小优化.
不用递归：
1 | 递归版(数组下标，先偶后奇，从0开始)： |
发现了什么吗？
最后的序列是原序列的二进制反转!
比如： $6 = (110)_2$ 反过来变成了 $(011)_2 = 3$ ！
如何得到二进制翻转后的数列？递推即可!
1 | for(RI i=0;i<n;++i)filp[i]=(filp[i>>1]>>1)|((i&1)?n>>1:0); |
Code:
1 |
|
luogu上的题，递归的总是T最后一个点，改成非递归版的就A了？
emmmmmmmmmmmmmm
所有优化全开：
很作死，建议不要轻易尝试[滑稽]
1 |
[滑稽][滑稽][滑稽][滑稽][滑稽][滑稽][滑稽][滑稽][滑稽][滑稽][滑稽]
NNT———学习笔记———关于FFT兄弟的那些事
0X5F—-NTT是啥?
NTT(快速数论变换)
一种快速数论变换算法，这种算法是以数论为基础，对样本点为的数论变换，按时间抽取的方法，得到一组等价的迭代方程，有效高速简化了方程中的计算公式·与直接计算相比，大大减少了运算次数。（见快速傅里叶变换）。
在计算机实现多项式乘法中，我们所熟知的快速傅里叶变换(FFT)是基于n次单位根$ω_{n}$ $(omega)$ 的优秀性质实现的，而由于其计算时会使用正弦函数和余弦函数，在不断运算时无法避免地会产生精度误差。而多项式乘法有些时候会建立在模域中，在对一些特殊的大质数取模时，便可以考虑用原根g来代替$ω_{n}$，而这些特殊的大质数的原根恰好满足$ω_{n}$的某些性质，这使得多项式乘法在模域中也可以快速的分治合并。 ———百度百科
实际上，$NTT$ 跟 $FFT$ 没啥差别，优缺点各有。优点，就是省掉了大精度的操作，常数较小。
贴出我在luogu的P3803测评记录：
O2—-FFT:
无优化—NTT:
(速度不在一个服务器……)
当然，什么东西都是有缺点的，$NTT$ 的缺点就是多项式的系数只能是整数 ，而且普通的 $NTT$ 并不能做到任意模数，比较有限制(但是像XZY这样的奆佬随手可以水过任意模数NTT)，不过对于一般的像998244353这样的模数可以跑。
实现的基础———原根
原根是一种数学符号，设 $m$ 是正整数，$a$ 是整数，若 $a$ 模 $m$ 的阶等于 $φ(m)$ ，则称 $a$ 为模 $m$ 的一个原根。（其中 $φ(m)$ 表示 $m$ 的欧拉函数）———百度百科
为什么 $FFT$ 可以如此优秀？那是因为单位根有着神奇的性质。原根也是如此！
合并的时候，$p=2len$ .
单位根：$cos\frac{2π}{P}+i sin\frac{2π}{P} = cos\frac{π}{len} + i sin\frac{π}{len}$
原根：$g^{\frac{MOD-1}{P}} = g^{\frac{MOD-1}{2len}}$
$NTT$ 的学习是建立在 $FFT$ 上的，建议大家先理解 $FFT$ 再来看 $NTT$
多说无益，贴板子吧……
1 |
|
那一题的代码：
1 |
|
0X3f3f3f3f 附记
来一张表吧：
| 模数 | G的值 |
|---|---|
| 3 | 2 |
| 5 | 2 |
| 17 | 3 |
| 97 | 5 |
| 193 | 5 |
| 257 | 3 |
| 7681 | 17 |
| 12289 | 11 |
| 40961 | 3 |
| 65537 | 3 |
| 786433 | 10 |
| 5767169 | 3 |
| 7340033 | 3 |
| 23068673 | 3 |
| 104857601 | 3 |
| 167772161 | 3 |
| 469762049 | 3 |
| 998244353 | 3 |
| 1004535809 | 3 |
| 2013265921 | 31 |
| 2281701377 | 3 |
| 3221225473 | 5 |
| 75161927681 | 3 |
| 77309411329 | 7 |
最后，因为本人实在太弱了，太蒟了，所以实在写不出啥了。
$by Qiuly$
本文标题:【算法】 浅谈FFT&学习笔记
文章作者:Qiuly
发布时间:2019年02月15日 - 00:00
最后更新:2019年05月06日 - 13:41
原始链接:http://qiulyblog.github.io/2019/02/15/[算法]FFT/
许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。